#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run22.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/5 0005 16:02
"""
"""
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
1.核心是中序遍历的非递归算法。
2.修改当前遍历节点与前一遍历节点的指针指向。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def Convert(self, pRootOfTree):
        if pRootOfTree is None:
            return None
        stack = []
        p = pRootOfTree
        # 用于保存中序遍历序列的上一节点
        pre = None
        isFirst = True
        while p is not None or len(stack) != 0:
            while p is not None:
                stack.append(p)
                p = p.left
            p = stack.pop()
            if isFirst:
                # 将中序遍历序列中的第一个节点记为root
                root = p
                pre = root
                isFirst = False
            else:
                pre.right = p
                p.left = pre
                pre = p
            p = p.right
        return pRootOfTree
